package com.lmk.dsa.algorithm.graph.miniTree;

import java.util.ArrayList;
import java.util.List;
import com.lmk.dsa.struct.commons.Edge;
import com.lmk.dsa.struct.graph.Graph;
import com.lmk.dsa.struct.graph.UnionFind;
import com.lmk.dsa.struct.heap.MinHeap;

/**
 * 克鲁斯卡尔（Kruskal）算法
 * @author LaoMake
 * @since 1.0
 */
public class Kruskal {

    /** 图的引用 */
    private Graph graph;

    /** 顶点的总数 */
    private int n;

    /** 最小生成树的边 */
    private List<Edge> edgeList;

    /** 用于存储边的最小堆 */
    private MinHeap heap;

    /** 最小生成树的总权值 */
    private int miniWeight;

    public Kruskal(Graph graph) {
        this.graph = graph;
        this.n = graph.vertexSize();
        this.edgeList = new ArrayList<>(n - 1);
        this.miniWeight = 0;
        this.heap = new MinHeap(graph.edgeSize());
    }

    public List<Edge> miniTree(){
        List<Edge> edges;
        for (int i = 0; i < n; i++) {
            edges = graph.adjoinEdge(i);
            for (Edge edge : edges){
                // 此处判断是为了避免将无向图中的两条边都放进堆中
                if(edge.from < edge.to){
                    heap.add(edge.weight, edge);
                }
            }
        }

        UnionFind unionFind = new UnionFind(n);
        Edge edge;
        while (!heap.isEmpty() && edgeList.size() < n - 1){
            edge = (Edge) heap.pool().value;

            // 如果这条边的两个顶点已经连接，则放弃这条边，以免形成环
            if(!unionFind.isConnected(edge.from, edge.to)){
                edgeList.add(edge);
                unionFind.union(edge.from, edge.to); // 连接两个顶点
            }
        }

        for (Edge e : edgeList){
            miniWeight += e.weight;
        }

        return edgeList;
    }

    public int getMiniWeight() {
        return miniWeight;
    }
}
